﻿#define _CRT_SECURE_NO_WARNINGS 1
//给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
//struct ListNode* reverseList(struct ListNode* head) {
//    struct ListNode* newHead = NULL;
//    struct ListNode* node;
//    while (head != NULL)
//    {
//        node = head;
//        head = head->next;
//        node->next = newHead;
//        newHead = node;
//    }
//    return newHead;
//}
//给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节
//struct ListNode* removeElements(struct ListNode* head, int val) {
//    if (head == NULL)
//        return head;
//    while (head != NULL && head->val == val)
//    {
//        struct ListNode* p = head;
//        head = head->next;
//        free(p);
//        p = NULL;
//    }
//    if (head == NULL)
//        return head;
//    struct ListNode* p = head;
//    struct ListNode* q = head->next;
//    while (q != NULL)
//    {
//        if (q->val == val)
//        {
//            while (p->next != q)
//            {
//                p = p->next;
//            }
//            struct ListNode* temp = q;
//            q = q->next;
//            p->next = q;
//            free(temp);
//            temp = NULL;
//        }
//        else
//        {
//            q = q->next;
//        }
//    }
//    return head;
//}
//法二
//struct ListNode* removeElements(struct ListNode* head, int val) {
//    struct ListNode* dummyHead = malloc(sizeof(struct ListNode));
//    dummyHead->next = head;
//    struct ListNode* temp = dummyHead;
//    while (temp->next != NULL) {
//        if (temp->next->val == val) {
//            temp->next = temp->next->next;
//        }
//        else {
//            temp = temp->next;
//        }
//    }
//    return dummyHead->next;
//}
//
//给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
//
//图示两个链表在节点 c1 开始相交：
//，先统计两个链表的长度
//还可以先统计两个链表的长度，如果两个链表的长度不一样，就让链表长的先走，直到两个链表长度一样，
//这个时候两个链表再同时每次往后移一步，看节点是否一样，如果有相等的，说明这个相等的节点就是两链表的交点，
//否则如果走完了还没有找到相等的节点，说明他们没有交点，直接返回null即可，来画个图看一下。


//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
//    int lenth1 = 0;
//    int lenth2 = 0;
//    struct ListNode* p = headA;
//    struct ListNode* q = headB;
//    if (headB == NULL || headA == NULL)
//        return NULL;
//    while (p != NULL)
//    {
//        p = p->next;
//        lenth1++;
//    }
//    while (q != NULL)
//    {
//        q = q->next;
//        lenth2++;
//    }
//    while (lenth1 != lenth2)
//    {
//        if (lenth1 > lenth2)
//        {
//            headA = headA->next;
//            lenth1--;
//        }
//        else
//        {
//            headB = headB->next;
//            lenth2--;
//        }
//    }
//    while (headA != headB)
//    {
//        headA = headA->next;
//        headB = headB->next;
//    }
//    return headA;
//}
//法二双指针
//struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
//    struct ListNode* temp = malloc(sizeof(struct ListNode));
//    temp->val = 0;
//    temp->next = head;
//    struct ListNode* fast = head;
//    struct ListNode* slow = temp;
//    for (int i = 0; i < n; i++)
//    {
//        fast = fast->next;
//    }
//    while (fast)
//    {
//        fast = fast->next;
//        slow = slow->next;
//    }
//    slow->next = slow->next->next;
//    return temp->next;
//}